package cn.edu.ncepu;

public class EulerTotient {

    /**
     * 计算欧拉函数φ(n)，即小于等于n且与n互质的正整数的个数
     * 实现思路：埃拉托斯特尼筛法变种，初始化phi[i]=i，然后遍历更新
     * @param n 输入的正整数
     * @return φ(n)的值
     */
    public static int eulerTotient(int n) {
        // 处理n=0的特殊情况（欧拉函数通常定义在正整数上，φ(0)无意义，此处按原逻辑返回0）
        if (n < 0) {
            throw new IllegalArgumentException("n必须为非负整数");
        }

        // 初始化phi数组，phi[i] = i，对应Python的phi = [i for i in range(0, n + 1)]
        int[] phi = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            phi[i] = i;
        }

        // 遍历1到n，更新后续的phi值
        for (int i = 1; i <= n; i++) {
            // 从i*2开始，步长i，对应Python的range(i << 1, n + 1, i)
            for (int j = i << 1; j <= n; j += i) {
                phi[j] -= phi[i];
            }
        }

        return phi[n];
    }

    public static void main(String[] args) {
        // 测试案例，与Python版本一致
        System.out.println(eulerTotient(10)); // 输出4，因为1,3,7,9与10互质
    }
}